package HuffmanTree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import HuffmanTree.Node;

public class HuffmanTree<T> {

    /**
     * 构造哈夫曼树
     *
     * @param forest n个结点组成的二叉树森林
     */
    public static <T> Node<T> createTree(List<Node<T>> forest) {
        while (forest.size() > 1) { // 哈夫曼树构造完成后,森林中只有一颗二叉树
            // 每次对森林中所有二叉树根节点权值排序
            Collections.sort(forest);
            // 找到2个权值之和最小的两颗二叉树
            Node<T> left = forest.get(forest.size() - 1);
            Node<T> right = forest.get(forest.size() - 2);
            // 由这两颗二叉树构造一颗新的二叉树(新二叉树的根节点权值为它们之和)
            Node<T> parent = new Node<T>((T) ("root-" + Math.random()), left.weight + right.weight);
            // 按照左子树权值小,按照右子树权值大
            if (left.weight <= right.weight) {
                parent.left = left;
                parent.right = right;
            } else {
                parent.left = right;
                parent.right = left;
            }
            left.parent = parent;
            right.parent = parent;
            // 从森林中删除这两颗二叉树
            forest.remove(left);
            forest.remove(right);
            // 把新构造的二叉树加入到森林中
            forest.add(parent);
        }
        forest.get(0).data = (T) "root";
        forest.get(0).parent = null;
        return forest.get(0);
    }

    /**
     * 获取哈夫曼树中所有结点
     */
    private static <T> List<Node<T>> getAllNodes(Node<T> root) {
        List<Node<T>> list = new ArrayList<Node<T>>();
        Queue<Node<T>> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node<T> pNode = queue.poll();
            list.add(pNode);
            if (pNode.left != null) {
                queue.add(pNode.left);
            }
            if (pNode.right != null) {
                queue.add(pNode.right);
            }
        }
        return list;
    }

    /**
     * 根据哈夫曼树进行哈夫曼编码
     */
    public static <T> void encode(Node<T> root) {
        StringBuilder builder = new StringBuilder();
        List<Node<T>> leafs = new ArrayList<Node<T>>();
        List<Node<T>> nodes = getAllNodes(root);

        // 获取哈夫曼树中所有叶子结点
        for (Node<T> node : nodes) {
            if (node.left == null && node.right == null) {
                leafs.add(node);
            }
        }

        // 从叶子到根寻找路径,完成编码
        for (Node<T> leaf : leafs) {
            builder.delete(0, builder.length());
            Node<T> node = leaf;
            while (!node.data.equals("root")) {
                Node<T> parent = node.parent;
                if (parent.left != null && parent.left.data.equals(node.data)) {
                    builder.append("0");
                }
                if (parent.right != null && parent.right.data.equals(node.data)) {
                    builder.append("1");
                }
                node = parent;
            }
            String strCode = builder.reverse().toString();
            System.out.println(leaf.data + ":" + strCode.toString());
        }
    }

}
